// stl_iterator.h

// #ifdef __STL_CLASS_PARTIAL_SPECIALIZATION

// This is the new version of reverse_iterator, as defined in the
// draft C++ standard. It relies on the iterator_traits template,
// which in turn relies on partial specialization. The class
// reverse_bidirectional_iterator is no longer part of the draft
// standard, but it is retained for backward compatibility.
template <class Iterator>
class reverse_iterator
{
protected:
	Iterator current;
public:
	typedef typename iterator_traits<Iterator>::iterator_category
		iterator_category;
	typedef typename iterator_traits<Iterator>::value_type
		value_type;
	typedef typename iterator_traits<Iterator>::difference_type
		difference_type;
	typedef typename iterator_traits<Iterator>::pointer
		pointer;
	typedef typename iterator_traits<Iterator>::reference
		reference;
	typedef Iterator iterator_type;
	typedef reverse_iterator<Iterator> self;
public:
	reverse_iterator() {}
	explicit reverse_iterator(iterator_type x) : current(x) {}
	reverse_iterator(const self& x) : current(x.current) {}
#ifdef __STL_MEMBER_TEMPLATES
	template <class Iter>
	reverse_iterator(const reverse_iterator<Iter>& x) : current(x.current) {}
#endif /* __STL_MEMBER_TEMPLATES */

	iterator_type base() const { return current; }
	reference operator*() const {
		Iterator tmp = current;
		return *--tmp;
	}
#ifndef __SGI_STL_NO_ARROW_OPERATOR
	pointer operator->() const { return &(operator*()); }
#endif /* __SGI_STL_NO_ARROW_OPERATOR */
	self& operator++() {
		--current;
		return *this;
	}
	self operator++(int) {
		self tmp = *this;
		--current;
		return tmp;
	}
	self& operator--() {
		++current;
		return *this;
	}
	self operator--(int) {
		self tmp = *this;
		++current;
		return tmp;
	}
	self operator+(difference_type n) const {
		return self(current - n);
	}
	self& operator+=(difference_type n) {
		current -= n;
		return *this;
	}
	self operator-(difference_type n) const {
		return self(current + n);
	}
	self& operator-=(difference_type n) {
		current += n;
		return *this;
	}
	reference operator[](difference_type n) const { return *(*this + n); }
};

template <class Iterator>
inline bool operator==(const reverse_iterator<Iterator>& x,
	                   const reverse_iterator<Iterator>& y) {
	return x.base() == y.base();
}
template <class Iterator>
inline bool operator<(const reverse_iterator<Iterator>& x,
	                  const reverse_iterator<Iterator>& y) {
	return y.base() < x.base();
}
template <class Iterator>
inline typename reverse_iterator<Iterator>::difference_type
operator-(const reverse_iterator<Iterator>& x,
	      const reverse_iterator<Iterator>& y) {
	return y.base() - x.base();
}
template <class Iterator>
inline reverse_iterator<Iterator>
operator+(reverse_iterator<Iterator>::difference_type n,
	      const reverse_iterator<Iterator>& x) {
	return reverse_iterator<Iterator>(x.base() - n);
}
// #else /* __STL_CLASS_PARTIAL_SPECIALIZATION */

// This is the old version of reverse_iterator, as found in the original
// HP STL. It does not use partial specialization.
template <class BidirectionalIterator, class T, class Reference = T&,
       	  class Distance = ptrdiff_t>
class reverse_bidirectional_iterator
{
	typedef reverse_bidirectional_iterator<BidirectionalIterator, T, Reference,
		Distance> self;
protected:
	BidirectionalIterator current;
public:
	typedef bidirectional_iterator_tag iterator_category;
	typedef T value_type;
	typedef Distance difference_type;
	typedef T* pointer;
	typedef Reference reference;
	reverse_bidirectional_iterator() {}
	explicit reverse_bidirectional_iterator(BidirectionalIterator x)
		: current(x) {}
	BidirectionalIterator base() const { return current; }
	Reference operator*() const {
		BidirectionalIterator tmp = current;
		return *--tmp;
	}

	pointer operator->() const { return &(operator*()); }

	self& operator++() {
		--current;
		return *this;
	}
	self operator++(int) {
		self tmp = *this;
		--current;
		return tmp;
	}
	self& operator--() {
		++current;
		return *this;
	}
	self operator--(int) {
		self tmp = *this;
		++current;
		return tmp;
	}
};


template <class RandomAccessIterator, class T, class Reference = T&,
	class Distance = ptrdiff_t>
class reverse_iterator
{
	typedef reverse_iterator<RandomAccessIterator, T, Reference, Distance>
		self;
protected:
	RandomAccessIterator current;
public:
	typedef random_access_iterator_tag iterator_category;
	typedef T value_type;
	typedef Distance difference_type;
	typedef T* pointer;
	typedef Reference reference;
	reverse_iterator() {}
	explicit reverse_iterator(RandomAccessIterator x) : current(x) {}
	RandomAccessIterator base() const { return current; }
	Reference operator*() const { return *(current - 1); }

	pointer operator->() const { return &(operator*()); }

	self& operator++() {
		--current;
		return *this;
	}
	self operator++(int) {
		self tmp = *this;
		--current;
		return tmp;
	}
	self& operator--() {
		++current;
		return *this;
	}
	self operator--(int) {
		self tmp = *this;
		++current;
		return tmp;
	}
	self operator+(Distance n) const {
		return self(current - n);
	}
	self& operator+=(Distance n) {
		current -= n;
		return *this;
	}
	self operator-(Distance n) const {
		return self(current + n);
	}
	self& operator-=(Distance n) {
		current += n;
		return *this;
	}
	Reference operator[](Distance n) const { return *(*this + n); }
};

// #endif //__STL_CLASS_PARTIAL_SPECIALIZATION